Video comprises a plurality of sequential pictures displayed one after another. Various techniques exist to convert video into digital form to facilitate transmission, storage, and manipulation. Unfortunately, digital video files in its raw data form are large and cumbersome. Various compression schemes have been developed to reduce the size of encoded pictures.
Each picture of a video may be encoded individually, either independent of other pictures of the video (intra-coding) or dependent on other pictures of the video (predictive coding). In video editing applications, intra-coding is often preferred for fast encoding and decoding. In video delivery applications such as DVD and broadcast, predictive coding is often used for better compression.
Various encoding schemes are known for compressing video. Many such schemes are block transform based (e.g., DCT-based), and operate by organizing each frame of the video into two-dimensional blocks. DCT coefficients for each block are then placed in a one-dimensional array in a defined pattern, typically in a zig-zag order through the block. That is, each block is processed independently of each other block, and the DCT coefficients are grouped block-by-block. The coefficients are then encoded using standard run-length/differential encoding according to a predetermined scan direction. For example, the one-dimensional array of coefficients can be converted to a list of run/level pairs, where “run” is the number of consecutive zero coefficients preceding a nonzero coefficient, and level is the value of the nonzero coefficient immediately following those zero coefficients.
The size of an encoded picture is influenced by its content, and therefore, it is difficult to precisely predict a file size of an encoded picture in advance. Generally, the selection of a quantizer is the single most significant factor affecting the resulting encoded picture size. However, changes to the quantizer do not always provide a predictable corresponding change to the picture's size. Only quantized coefficients quantized to nonzero values with a first smaller quantizer may potentially become smaller (and therefore requiring fewer bits to encode) when quantized with the second larger quantizer. Any coefficient that is quantized to zero with the first quantizer will remain zero when quantized with the second larger quantizer, therefore not affecting the picture size. Furthermore, the number of bits saved by using a second larger quantizer is typically different for different coefficients depending on their values. It also depends on values of nearby coefficients because consecutive zeros are coded as one “run” symbol.
It is often desirable to encode a video picture to a specified size for storage, transmission, and performance (encoding and decoding speed) constraints. One approach to enforce such a size requirement is to process each macroblock in the image sequentially, progressively adjusting the quantizer as the encoder encodes the picture. A typical approach is to calculate the average macroblock size and keep track of the number of bits used so far. Before encoding a macroblock, the encoder checks the number of bits it has used up to this point. If it is using more bits than allocated, it uses a larger quantization step size for the next macroblock. If it is using fewer bits than allocated, it uses a smaller quantization step size for the next macroblock. Unfortunately, this sequential approach is difficult to execute simultaneously across a plurality of processors. In addition, an encoded picture may be encoded with many different quantizers, resulting in undesirable variance in visual quality from one macroblock to another when decoded and displayed. Further, the same quantization step size is unlikely to be used again when the image is decoded and re-encoded during the editing process, resulting in nontrivial multi-generation quality loss.